package com.leetcode.algorithm.y22.m06;

/**
 * 96. 不同的二叉搜索树
 * 
 * https://leetcode.cn/problems/unique-binary-search-trees/
 * 
 * @author jie.deng
 *
 */
class Question0096Solution01 {
	
	public int numTrees(int n) {
		// DP状态定义
		// dp[i]表示i个节点组成二叉搜索树的种数
		int[] dp = new int[n + 1];
		// DP状态初始化
		dp[0] = 1;

		// DP状态转移方程
		for (int i = 1; i <= n; i++) {
			// j表示左子树节点个数, i-j-1表示右子树节点个数
			for (int j = 0; j < i; j++) {
				dp[i] += dp[j] * dp[i - j - 1];
			}
		}

		return dp[n];
	}
    
}